import { Compareable } from '../binarySearchTree'

/**
 * NOTE: 堆(二叉树的堆)的基本结构:
 * 1. 完全二叉树: 将元素排列为一层一层的树结构, 从左向右的排列
 * 2. 任意一个节点的值总是不大于父节点的值, 那么根节点的值是最大的
 * => 最大堆;
 * 规律: (使用数组的来实现二叉堆) 节点从 1 开始
 *  parent: (i) = (ceil(i/2))
 *  left child (i) = 2*i
 *  right child (i) = 2*i + 1
 *  (使用数学归纳法来证明)
 * 那么从 0 开始的话:
 *  parent: (i) = (ceil((i - 1)/2))
 *  left child (i) = 2*i + 1
 *  right child (i) = 2*i + 2
 */

 /**
  * NOTE: 最小堆可以通过自己实现 HeapNode 的 compare 方法来自定义 大与小含义
  */

export class HeapNode implements Compareable<HeapNode> {
  private v!: number

  constructor(v: number) {
    this.v = v
    // console.log(this.data)
  }

  /**
   * 比较两个节点的大小: 当前的节点大于 node 节点 放回 1
   * @param node
   */
  public compare(node: HeapNode): 0 | 1 | -1 {
    let r: 0 | 1 | -1 = 1
    if (this.getCompareValue() > node.getCompareValue()) {
      r = 1
    } else if (this.getCompareValue() < node.getCompareValue()) {
      r = -1
    } else {
      r = 0
    }
    return r
  }

  public getCompareValue(): number {
    return this.v
  }

}

export class MaxHeap {
  // 完全二叉树: 使用数组作为底层的数据结构
  private data: HeapNode[] = []
  constructor(cap?: number) {
    if (cap) {
      this.data = new Array<HeapNode>(cap)
    }
  }

  /**
   * isEmpty
   */
  public isEmpty(): boolean {
    return this.data.length === 0
  }

  /**
   * getSize
   */
  public getSize() {
    return this.data.length
  }

  /**
   * add: O(logN)
   */
  public add(e: HeapNode) {
    this.data.push(e)
    // 向数组的最后添加一个元素, 然后将这个元素上浮到对应的位置
    this.siftUp(this.data.length - 1)
  }

  /**
   * replace: 取出最大的元素后, 再放入一个元素, 直接将堆顶元素替换, 然后在下浮
   */
  public replace(e: HeapNode): HeapNode {
    let ret = this.findMax()
    this.data[0] = e
    this.siftDown(0)
    return ret
  }

  /**
   * heapify: 将任意的数组转换成一个堆 O(N)
   * 如果是逐步的添加的话, 那么就是 O(nlogn)
   */
  public heapify(arr: number[]) {
    this.data = new Array(arr.length)
    for (let i = 0; i < arr.length; i++) {
      this.data[i] = new HeapNode(arr[i])
    }
    // 从最后一个非叶子节点的索引开始, 执行下浮的操作,
    // NOTE: 获取最后一个非叶子节点的索引: 获取最后一个叶子节点的索引, 再找父节点
    let last = this.data.length - 1
    let start = this.getParentIndex(last)
    for (let i = start; i >= 0; i--) {
      this.siftDown(i)
    }
  }

  /**
   * getMax: O(logN)
   */
  public extractMax(): HeapNode {
    // 将最后一个元素临时提到根节点, 然后在下浮到对应的位置,
    let e = this.findMax()
    this.swap(0, this.data.length - 1)
    this.data.pop()
    this.siftDown(0)
    return e
  }

  /**
   * findMax
   */
  public findMax(): HeapNode {
    if (this.data.length === 0) {
      throw new Error('heap is empty')
    }
    return this.data[0]
  }

  /**
   * print
   */
  public print() {
    this.data.forEach((e) => {
      console.log(e.getCompareValue())
    })
  }

  // 节点下浮: 下浮和两个孩子进行比较, 然后进行和最大的交换位置
  private siftDown(i: number) {
    while (this.getLeftChildIndex(i) < this.data.length) {
      // j 初始化为左孩子的索引
      let j = this.getLeftChildIndex(i)
      let rightIndex = j + 1
      // 左孩子的索引要小于数组的长度
      if (rightIndex < this.data.length &&
        this.data[rightIndex].compare(this.data[j]) > 0) {
        // 如果右节点 大于 左节点; 那么说明需要和右孩子进行交换位置, 那么重新赋值 j
        j = this.getRightChildIndex(i)
      }

      // 如果当前位置又大于了 j 位置的 说明不需要进行交换了, 直接退出循环
      if (this.data[i].compare(this.data[j]) > 0) {
        break
      }

      this.swap(i, j)

      i = j
    }
  }

  // 节点上浮: 和父节点进行比较
  private siftUp(i: number) {
    while (i > 0 && this.data[this.getParentIndex(i)].compare(this.data[i]) < 0) {
      this.swap(i, this.getParentIndex(i))
      i = this.getParentIndex(i)
    }
  }

  private swap(i: number, j: number) {
    if (i < 0 || i >= this.data.length || j < 0 || j >= this.data.length) {
      throw new Error('index error')
    }

    let temp = this.data[i]
    this.data[i] = this.data[j]
    this.data[j] = temp
  }

  private getParentIndex(i: number): number {
    if (i === 0) {
      throw new Error('0 index does not have parent node')
    }
    return Math.ceil((i - 1) / 2)
  }

  private getLeftChildIndex(i: number): number {
    return i * 2 + 1
  }

  private getRightChildIndex(i: number): number {
    return i * 2 + 2
  }

}
